SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Computable function</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Computable function</span></span>

</h1>

</header>

<p><b>Computable functions</b> are the basic objects of study in <a href="Computability_theory" title="Computability theory">computability theory</a>. Informally, a <a href="Function_(mathematics)" title="Function (mathematics)">function</a> is <i>computable</i> if there is an <a href="Algorithm" title="Algorithm">algorithm</a> that computes the value of the function for every value of its argument. Because of the lack of a precise definition of the concept of algorithm, every formal definition of computability must refer to a specific <a href="Model_of_computation" title="Model of computation">model of computation</a>.

</p><p>Many such models of computation have been proposed, the major ones being <a href="Turing_machine" title="Turing machine">Turing machines</a>, <a href="Register_machine" title="Register machine">register machines</a>, <a href="Lambda_calculus" title="Lambda calculus">lambda calculus</a> and <a href="General_recursive_function" title="General recursive function">general recursive functions</a>. Although these four are of a very different nature, they provide exactly the same class of computable functions, and, for every model of computation that has ever been proposed, the computable functions for such a model are computable for the above four models of computation.

</p><p>The <a href="Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a> is the unprovable assertion that every notion of computability that can be imagined can compute only functions that are computable in the above sense.

</p><p>Before the precise definition of computable functions, <a href="Mathematician" title="Mathematician">mathematicians</a> often used the informal term <i>effectively calculable</i>. This term has since come to be identified with the computable functions. The effective computability of these functions does not imply that they can be <i>efficiently</i> computed (i.e. computed within a reasonable amount of time). In fact, for some effectively calculable functions it can be shown that any algorithm that computes them will be very inefficient in the sense that the running time of the algorithm increases <a href="Exponential_growth" title="Exponential growth">exponentially</a> (or even <a href="Tetration" title="Tetration">superexponentially</a>) with the length of the input. The fields of <a href="Feasible_computability" class="mw-redirect" title="Feasible computability">feasible computability</a> and <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity</a> study functions that can be computed efficiently.

</p><p>The <a href="Blum_axioms" title="Blum axioms">Blum axioms</a> can be used to define an abstract <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity theory</a> on the set of computable functions. In computational complexity theory, the problem of computing the value of a function is known as a <a href="Function_problem" title="Function problem">function problem</a>, by contrast to <a href="Decision_problem" title="Decision problem">decision problems</a> whose results are either "yes" of "no".

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">See also: <a href="Total_Turing_machine" class="mw-redirect" title="Total Turing machine">Total Turing machine</a></div>

<p>Computability of a function is an informal notion. One way to describe it is to say that a function is computable if its value can be obtained by an <a href="Effective_method" title="Effective method">effective procedure</a>. With more rigor, a function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }">

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }</annotation>

</semantics>

</math></span><img src="./093f78de2a24bc3f255b95655e98045f9eae0a37.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.275ex; height:3.009ex;" alt="{\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }" loading="lazy"></span>

is computable if and only if there is an effective procedure that, given any <span class="texhtml mvar" style="font-style:italic;">k</span>-<a href="Tuple" title="Tuple">tuple</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} }</annotation>

</semantics>

</math></span><img src="./32adf004df5eb0a8c7fd8c0b6b7405183c5a5ef2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.411ex; height:1.676ex;" alt="{\displaystyle \mathbf {x} }" loading="lazy"></span> of natural numbers, will produce the value <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(\mathbf {x} )}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(\mathbf {x} )}</annotation>

</semantics>

</math></span><img src="./e41ea95e6949bf4cef6426116364ba87e0fdcd60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.499ex; height:2.843ex;" alt="{\displaystyle f(\mathbf {x} )}" loading="lazy"></span>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> In agreement with this definition, the remainder of this article presumes that computable functions take finitely many <a href="Natural_numbers" class="mw-redirect" title="Natural numbers">natural numbers</a> as arguments and produce a value which is a single natural number.

</p><p>As counterparts to this informal description, there exist multiple formal, mathematical definitions. The class of computable functions can be defined in many equivalent <a href="Model_of_computation" title="Model of computation">models of computation</a>, including

</p>

<ul><li><a href="Turing_machine" title="Turing machine">Turing machines</a></li>

<li><a href="General_recursive_function" title="General recursive function">General recursive functions</a></li>

<li><a href="Lambda_calculus" title="Lambda calculus">Lambda calculus</a></li>

<li>Post machines (<a href="Post%E2%80%93Turing_machine" title="Post–Turing machine">Post–Turing machines</a> and <a href="Tag_system" title="Tag system">tag machines</a>).</li>

<li><a href="Register_machine" title="Register machine">Register machines</a></li></ul>

<p>Although these models use different representations for the functions, their inputs, and their outputs, translations exist between any two models, and so every model describes essentially the same class of functions, giving rise to the opinion that formal computability is both natural and not too narrow.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> These functions are sometimes referred to as "recursive", to contrast with the informal term "computable",<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> a distinction stemming from a 1934 discussion between Kleene and Gödel.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup><sup>p.6</sup>

</p><p>For example, one can formalize computable functions as <a href="%CE%9C-recursive_function" class="mw-redirect" title="Μ-recursive function">μ-recursive functions</a>, which are <a href="Partial_function" title="Partial function">partial functions</a> that take finite <a href="Tuple" title="Tuple">tuples</a> of <a href="Natural_number" title="Natural number">natural numbers</a> and return a single natural number (just as above). They are the smallest class of partial functions that includes the constant, successor, and projection functions, and is <a href="Closure_(mathematics)" title="Closure (mathematics)">closed</a> under <a href="Function_composition" title="Function composition">composition</a>, <a href="Primitive_recursive_function" title="Primitive recursive function">primitive recursion</a>, and the <a href="%CE%9C_operator" title="Μ operator">μ operator</a>.

</p><p>Equivalently, computable functions can be formalized as functions which can be calculated by an idealized computing agent such as a <a href="Turing_machine" title="Turing machine">Turing machine</a> or a <a href="Register_machine" title="Register machine">register machine</a>. Formally speaking, a <a href="Partial_function" title="Partial function">partial function</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }">

<msup>

</mrow>

</mrow>

</msup>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f:\mathbb {N} ^{k}\rightarrow \mathbb {N} }</annotation>

</semantics>

</p>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(\mathbf {x} )}</annotation>

</semantics>

</math></span><img src="./e41ea95e6949bf4cef6426116364ba87e0fdcd60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.499ex; height:2.843ex;" alt="{\displaystyle f(\mathbf {x} )}" loading="lazy"></span> is defined, then the program will terminate on the input <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} }</annotation>

</semantics>

</math></span><img src="./32adf004df5eb0a8c7fd8c0b6b7405183c5a5ef2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.411ex; height:1.676ex;" alt="{\displaystyle \mathbf {x} }" loading="lazy"></span> with the value <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle f(\mathbf {x} )}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(\mathbf {x} )}</annotation>

</semantics>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle f(\mathbf {x} )}</annotation>

</semantics>

</math></span><img src="./e41ea95e6949bf4cef6426116364ba87e0fdcd60.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.499ex; height:2.843ex;" alt="{\displaystyle f(\mathbf {x} )}" loading="lazy"></span> is undefined, then the program never terminates on the input <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbf {x} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbf {x} }</annotation>

</semantics>

<div class="mw-heading mw-heading2"><h2 id="Characteristics_of_computable_functions">Characteristics of computable functions</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Algorithm" title="Algorithm">Algorithm</a></div>

<p>The basic characteristic of a computable function is that there must be a finite procedure (an <a href="Algorithm" title="Algorithm">algorithm</a>) telling how to compute the function. The models of computation listed above give different interpretations of what a procedure is and how it is used, but these interpretations share many properties. The fact that these models give equivalent classes of computable functions stems from the fact that each model is capable of reading and mimicking a procedure for any of the other models, much as a <a href="Compiler" title="Compiler">compiler</a> is able to read instructions in one computer language and emit instructions in another language.

</p><p><a href="Herbert_Enderton" title="Herbert Enderton">Enderton</a> [1977] gives the following characteristics of a procedure for computing a computable function; similar characterizations have been given by Turing [1936], Rogers [1967], and others.

</p>

<ul><li>"There must be exact instructions (i.e. a program), finite in length, for the procedure." Thus every computable function must have a finite program that completely describes how the function is to be computed. It is possible to compute the function by just following the instructions; no guessing or special insight is required.</li>

<li>"If the procedure is given a <i>k</i>-tuple <b>x</b> in the domain of <i>f</i>, then after a finite number of discrete steps the procedure must terminate and produce <i>f</i>(<b>x</b>)." Intuitively, the procedure proceeds step by step, with a specific rule to cover what to do at each step of the calculation. Only finitely many steps can be carried out before the value of the function is returned.</li>

<li>"If the procedure is given a <i>k</i>-tuple <b>x</b> which is not in the domain of <i>f</i>, then the procedure might go on forever, never halting. Or it might get stuck at some point (i.e., one of its instructions cannot be executed), but it must not pretend to produce a value for <i>f</i> at <b>x</b>." Thus if a value for <i>f</i>(<b>x</b>) is ever found, it must be the correct value. It is not necessary for the computing agent to distinguish correct outcomes from incorrect ones because the procedure is defined as correct if and only if it produces an outcome.</li></ul>

<p>Enderton goes on to list several clarifications of these 3 requirements of the procedure for a computable function:

</p>

<ol><li>The procedure must theoretically work for arbitrarily large arguments. It is not assumed that the arguments are smaller than the number of atoms in the Earth, for example.</li>

<li>The procedure is required to halt after finitely many steps in order to produce an output, but it may take arbitrarily many steps before halting. No time limitation is assumed.</li>

<li>Although the procedure may use only a finite amount of storage space during a successful computation, there is no bound on the amount of space that is used. It is assumed that additional storage space can be given to the procedure whenever the procedure asks for it.</li></ol>

<p>To summarise, based on this view a function is computable if:

</p>

<div><ol style="list-style-type:lower-alpha"><li>given an input from its domain, possibly relying on unbounded storage space, it can give the corresponding output by following a procedure (program, algorithm) that is formed by a finite number of exact unambiguous instructions;</li><li>it returns such output (halts) in a finite number of steps; and</li><li>if given an input which is not in its domain it either never halts or it gets stuck.</li></ol></div>

<p>The field of <a href="Computational_complexity_theory" title="Computational complexity theory">computational complexity</a> studies functions with prescribed bounds on the time and/or space allowed in a successful computation.

</p>

<div class="mw-heading mw-heading2"><h2 id="Computable_sets_and_relations">Computable sets and relations</h2></div>

<p>A set <span class="texhtml"><var>A</var></span> of natural numbers is called <b><a href="Computable_set" title="Computable set">computable</a></b> (synonyms: <b>recursive</b>, <b>decidable</b>) if there is a computable, total function <span class="texhtml"><i>f</i></span> such that for any natural number <span class="texhtml"><var>n</var></span>, <span class="texhtml"><i>f</i>(<var>n</var>) = 1</span> if <span class="texhtml"><var>n</var></span> is in <span class="texhtml"><var>A</var></span> and <span class="texhtml"><i>f</i>(<var>n</var>) = 0</span> if <span class="texhtml"><var>n</var></span> is not in <span class="texhtml"><var>A</var></span>.

</p><p>A set of natural numbers is called <b><a href="Computably_enumerable_set" title="Computably enumerable set">computably enumerable</a></b> (synonyms: <b>recursively enumerable</b>, <b>semidecidable</b>) if there is a computable function <span class="texhtml"><i>f</i></span> such that for each number <span class="texhtml"><var>n</var></span>, <span class="texhtml"><i>f</i>(<var>n</var>)</span> is defined <a href="If_and_only_if" title="If and only if">if and only if</a> <span class="texhtml"><var>n</var></span> is in the set. Thus a set is computably enumerable if and only if it is the domain of some computable function. The word <i>enumerable</i> is used because the following are equivalent for a nonempty subset <span class="texhtml"><var>B</var></span> of the natural numbers:

</p>

<ul><li><span class="texhtml"><var>B</var></span> is the domain of a computable function.</li>

<li><span class="texhtml"><var>B</var></span> is the range of a total computable function. If <span class="texhtml"><var>B</var></span> is infinite then the function can be assumed to be <a href="Injective" class="mw-redirect" title="Injective">injective</a>.</li></ul>

<p>If a set <span class="texhtml"><var>B</var></span> is the range of a function <span class="texhtml"><i>f</i></span> then the function can be viewed as an

enumeration of <span class="texhtml"><var>B</var></span>, because the list <span class="texhtml"><i>f</i>(0), <i>f</i>(1), ...</span> will include every element of <span class="texhtml"><var>B</var></span>.

</p><p>Because each <a href="Finitary_relation" title="Finitary relation">finitary relation</a> on the natural numbers can be identified with a corresponding set of finite sequences of natural numbers, the notions of <b>computable relation</b> and <b>computably enumerable relation</b> can be defined from their analogues for sets.

</p>

<div class="mw-heading mw-heading2"><h2 id="Formal_languages">Formal languages</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Formal_language" title="Formal language">Formal language</a></div>

<p>In <a href="Computability_theory_(computer_science)" class="mw-redirect" title="Computability theory (computer science)">computability theory in computer science</a>, it is common to consider <a href="Formal_language" title="Formal language">formal languages</a>. An <b>alphabet</b> is an arbitrary set. A <b>word</b> on an alphabet is a finite sequence of symbols from the alphabet; the same symbol may be used more than once. For example, binary strings are exactly the words on the alphabet <span class="texhtml">{0, 1</span>}. A <b>language</b> is a subset of the collection of all words on a fixed alphabet. For example, the collection of all binary strings that contain exactly 3 ones is a language over the binary alphabet.

</p><p>A key property of a formal language is the level of difficulty required to decide whether a given word is in the language. Some coding system must be developed to allow a computable function to take an arbitrary word in the language as input; this is usually considered routine. A language is called <b>computable</b> (synonyms: <b>recursive</b>, <b>decidable</b>) if there is a computable function <span class="texhtml"><i>f</i></span> such that for each word <span class="texhtml"><var>w</var></span> over the alphabet, <span class="texhtml"><i>f</i>(<var>w</var>) = 1</span> if the word is in the language and <span class="texhtml"><i>f</i>(<var>w</var>) = 0</span> if the word is not in the language. Thus a language is computable just in case there is a procedure that is able to correctly tell whether arbitrary words are in the language.

</p><p>A language is <b>computably enumerable</b> (synonyms: <b>recursively enumerable</b>, <b>semidecidable</b>) if there is a computable function <span class="texhtml"><i>f</i></span> such that <span class="texhtml"><i>f</i>(<var>w</var>)</span> is defined if and only if the word <span class="texhtml"><var>w</var></span> is in the language. The term <i>enumerable</i> has the same etymology as in computably enumerable sets of natural numbers.

</p>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

<p>The following functions are computable:

</p>

<ul><li>Each function with a finite <a href="Domain_of_a_function" title="Domain of a function">domain</a>; e.g., any finite sequence of natural numbers.</li>

<li>Each <a href="Constant_function" title="Constant function">constant function</a> <i>f</i> : <b>N</b><sup><i>k</i></sup> → <b>N</b>, <i>f</i>(<i>n</i><sub>1</sub>,...<i>n</i><sub><i>k</i></sub>) := <i>n</i>.</li>

<li><a href="Addition" title="Addition">Addition</a> <i>f</i> : <b>N</b><sup>2</sup> → <b>N</b>, <i>f</i>(<i>n</i><sub>1</sub>,<i>n</i><sub><i>2</i></sub>) := <i>n</i><sub>1</sub> + <i>n</i><sub>2</sub></li>

<li>The <a href="Greatest_common_divisor" title="Greatest common divisor">greatest common divisor</a> of two numbers</li>

<li>A <a href="B%C3%A9zout_coefficient" class="mw-redirect" title="Bézout coefficient">Bézout coefficient</a> of two numbers</li>

<li>The smallest <a href="Prime_factor" class="mw-redirect" title="Prime factor">prime factor</a> of a number</li></ul>

<p>If <i>f</i> and <i>g</i> are computable, then so are: <i>f</i> + <i>g</i>, <a href="Multiplication" title="Multiplication"><i>f</i> * <i>g</i></a>, <a href="Function_composition" title="Function composition"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \color {Blue}f\circ g}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \color {Blue}f\circ g}</annotation>

</semantics>

</math></span><img src="./9bc7cb6de47eaf3003200d5334bcfdfa76f60f4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.589ex; height:2.509ex;" alt="{\displaystyle \color {Blue}f\circ g}" loading="lazy"></span></a> if

<i>f</i> is <a href="Unary_operation" title="Unary operation">unary</a>, max(<i>f</i>,<i>g</i>), min(<i>f</i>,<i>g</i>), <span class="texhtml"><a href="Arg_max" title="Arg max">arg max</a>{<i>y</i> ≤ <i>f</i>(<i>x</i>)}</span> and many more combinations.

</p><p>The following examples illustrate that a function may be computable though it is not known which algorithm computes it.

</p>

<ul><li>The function <i>f</i> such that <i>f</i>(<i>n</i>) = 1 if there is a sequence of <i>at least n</i> consecutive fives in the decimal expansion of <span class="texhtml mvar" style="font-style:italic;">π</span>, and <i>f</i>(<i>n</i>) = 0 otherwise, is computable. (The function <i>f</i> is either the constant 1 function, which is computable, or else there is a <i>k</i> such that <i>f</i>(<i>n</i>) = 1 if <i>n</i> < <i>k</i> and <i>f</i>(<i>n</i>) = 0 if <i>n</i> ≥ <i>k</i>. Every such function is computable. It is not known whether there are arbitrarily long runs of fives in the decimal expansion of π, so we don't know <i>which</i> of those functions is <i>f</i>. Nevertheless, we know that the function <i>f</i> must be computable.)</li>

<li>Each finite segment of an <i>un</i>computable sequence of natural numbers (such as the <a href="Busy_beaver#Score_function_Σ" title="Busy beaver">Busy Beaver function</a> Σ) is computable. E.g., for each natural number <i>n</i>, there exists an algorithm that computes the finite sequence Σ(0), Σ(1), Σ(2), ..., Σ(<i>n</i>) — in contrast to the fact that there is no algorithm that computes the <i>entire</i> Σ-sequence, i.e. Σ(<i>n</i>) for all <i>n</i>. Thus, "Print 0, 1, 4, 6, 13" is a trivial algorithm to compute Σ(0), Σ(1), Σ(2), Σ(3), Σ(4); similarly, for any given value of <i>n</i>, such a trivial algorithm <i>exists</i> (even though it may never be <i>known</i> or produced by anyone) to compute Σ(0), Σ(1), Σ(2), ..., Σ(<i>n</i>).</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Church–Turing_thesis">Church–Turing thesis</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a></div>

<p>The <b>Church–Turing thesis</b> states that any function computable from a procedure possessing the three properties listed <a href="#Characteristics_of_computable_functions">above</a> is a computable function. Because these three properties are not formally stated, the Church–Turing thesis cannot be proved. The following facts are often taken as evidence for the thesis:

</p>

<ul><li>Many equivalent models of computation are known, and they all give the same definition of computable function (or a weaker version, in some instances).</li>

<li>No stronger model of computation which is generally considered to be <a href="Effectively_calculable" class="mw-redirect" title="Effectively calculable">effectively calculable</a> has been proposed.</li></ul>

<p>The Church–Turing thesis is sometimes used in proofs to justify that a particular function is computable by giving a concrete description of a procedure for the computation. This is permitted because it is believed that all such uses of the thesis can be removed by the tedious process of writing a formal procedure for the function in some model of computation.

</p>

<div class="mw-heading mw-heading2"><h2 id="Provability">Provability</h2></div>

<p>Given a function (or, similarly, a set), one may be interested not only if it is computable, but also whether this can be <i>proven</i> in a particular proof system (usually <a href="First-order_logic" title="First-order logic">first order</a> <a href="Peano_arithmetic" class="mw-redirect" title="Peano arithmetic">Peano arithmetic</a>). A function that can be proven to be computable is called <b>provably total</b>.

</p><p>The set of provably total functions is <a href="Recursively_enumerable" class="mw-redirect" title="Recursively enumerable">recursively enumerable</a>: one can enumerate all the provably total functions by enumerating all their corresponding proofs, that prove their computability. This can be done by enumerating all the proofs of the proof system and ignoring irrelevant ones.

</p>

<div class="mw-heading mw-heading3"><h3 id="Relation_to_recursively_defined_functions">Relation to recursively defined functions</h3></div>

<p>In a function defined by a <a href="Recursive_definition" title="Recursive definition">recursive definition</a>, each value is defined by a fixed first-order formula of other, previously defined values of the same function or other functions, which might be simply constants. A subset of these is the <a href="Primitive_recursive_function" title="Primitive recursive function">primitive recursive functions</a>. Another example is the <a href="Ackermann_function" title="Ackermann function">Ackermann function</a>, which is recursively defined but not primitive recursive.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup>

</p><p>For definitions of this type to avoid circularity or infinite regress, it is necessary that recursive calls to the same function within a definition be to arguments that are smaller in some <a href="Well-partial-order" class="mw-redirect" title="Well-partial-order">well-partial-order</a> on the function's domain. For instance, for the Ackermann function <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span>, whenever the definition of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(x,y)}</annotation>

</semantics>

</math></span><img src="./301b7810250db19125d15b511054cc06fd5f9a2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.072ex; height:2.843ex;" alt="{\displaystyle A(x,y)}" loading="lazy"></span> refers to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A(p,q)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A(p,q)}</annotation>

</semantics>

</math></span><img src="./ba41102b72169e9da4c85d3a812c5e7a42ef30a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.825ex; height:2.843ex;" alt="{\displaystyle A(p,q)}" loading="lazy"></span>, then <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (p,q)<(x,y)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (p,q)<(x,y)}</annotation>

</semantics>

</math></span><img src="./10984ed60721beae77bdb5ff4b3cfb4c99003dc6.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.509ex; height:2.843ex;" alt="{\displaystyle (p,q)<(x,y)}" loading="lazy"></span> w.r.t. the <a href="Lexicographic_order" title="Lexicographic order">lexicographic order</a> on pairs of <a href="Natural_number" title="Natural number">natural numbers</a>. In this case, and in the case of the primitive recursive functions, well-ordering is obvious, but some "refers-to" relations are nontrivial to prove as being well-orderings. Any function defined recursively in a well-ordered way is computable: each value can be computed by expanding a tree of recursive calls to the function, and this expansion must terminate after a finite number of calls, because otherwise <a href="K%C5%91nig's_lemma" title="Kőnig's lemma">Kőnig's lemma</a> would lead to an infinite descending sequence of calls, violating the assumption of well-ordering.

</p>

<div class="mw-heading mw-heading3"><h3 id="Total_functions_that_are_not_provably_total">Total functions that are not provably total</h3></div>

<p>In a <a href="Soundness" title="Soundness">sound</a> proof system, every provably total function is indeed total, but the converse is not true: in every first-order proof system that is strong enough and sound (including Peano arithmetic), one can prove (in another proof system) the existence of total functions that cannot be proven total in the proof system.

</p><p>If the total computable functions are enumerated via the Turing machines that produces them, then the above statement can be shown, if the proof system is sound, by a similar diagonalization argument to that used above, using the enumeration of provably total functions given earlier. One uses a Turing machine that enumerates the relevant proofs, and for every input <i>n</i> calls <i>f</i><sub><i>n</i></sub>(<i>n</i>) (where <i>f</i><sub><i>n</i></sub> is <i>n</i>-th function by <i>this</i> enumeration) by invoking the Turing machine that computes it according to the n-th proof. Such a Turing machine is guaranteed to halt if the proof system is sound.

</p>

<div class="mw-heading mw-heading2"><h2 id="Uncomputable_functions_and_unsolvable_problems">Uncomputable functions and unsolvable problems</h2></div>

<div role="note" class="hatnote navigation-not-searchable">Main article: <a href="List_of_undecidable_problems" title="List of undecidable problems">List of undecidable problems</a></div>

<p>Every computable function has a finite procedure giving explicit, unambiguous instructions on how to compute it. Furthermore, this procedure has to be encoded in the finite alphabet used by the computational model, so there are only <a href="Countability" class="mw-redirect" title="Countability">countably</a> many computable functions. For example, functions may be encoded using a string of bits (the alphabet <span class="texhtml">Σ = {0, 1</span>}).

</p><p>The real numbers are uncountable so most real numbers are not computable. See <a href="Computable_number#Properties" title="Computable number">computable number</a>. The set of <a href="Finitary" title="Finitary">finitary</a> functions on the natural numbers is uncountable so most are not computable. Concrete examples of such functions are <a href="Busy_beaver" title="Busy beaver">Busy beaver</a>, <a href="Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a>, or any function that outputs the digits of a noncomputable number, such as <a href="Chaitin's_constant" title="Chaitin's constant">Chaitin's constant</a>.

</p><p>Similarly, most subsets of the natural numbers are not computable. The <a href="Halting_problem" title="Halting problem">halting problem</a> was the first such set to be constructed. The <a href="Entscheidungsproblem" title="Entscheidungsproblem">Entscheidungsproblem</a>, proposed by <a href="David_Hilbert" title="David Hilbert">David Hilbert</a>, asked whether there is an effective procedure to determine which mathematical statements (coded as natural numbers) are true. Turing and Church independently showed in the 1930s that this set of natural numbers is not computable. According to the Church–Turing thesis, there is no effective procedure (with an algorithm) which can perform these computations.

</p>

<div class="mw-heading mw-heading2"><h2 id="Extensions_of_computability">Extensions of computability</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Relative_computability">Relative computability</h3></div>

<p>The notion of computability of a function can be <a href="Relative_computability" class="mw-redirect" title="Relative computability">relativized</a> to an arbitrary <a href="Set_(mathematics)" title="Set (mathematics)">set</a> of <a href="Natural_number" title="Natural number">natural numbers</a> <i>A</i>. A function <i>f</i> is defined to be <b>computable in <i>A</i></b> (equivalently <b><i>A</i>-computable</b> or <b>computable relative to <i>A</i></b>) when it satisfies the definition of a computable function with modifications allowing access to <i>A</i> as an <a href="Oracle_(computability)" class="mw-redirect" title="Oracle (computability)">oracle</a>. As with the concept of a computable function relative computability can be given equivalent definitions in many different models of computation. This is commonly accomplished by supplementing the model of computation with an additional primitive operation which asks whether a given integer is a member of <i>A</i>. We can also talk about <i>f</i> being <b>computable in <i>g</i></b> by identifying <i>g</i> with its graph.

</p>

<div class="mw-heading mw-heading3"><h3 id="Higher_recursion_theory">Higher recursion theory</h3></div>

<p><a href="Hyperarithmetical_theory" title="Hyperarithmetical theory">Hyperarithmetical theory</a> studies those sets that can be computed from a <a href="Computable_ordinal" title="Computable ordinal">computable ordinal</a> number of iterates of the <a href="Turing_jump" title="Turing jump">Turing jump</a> of the empty set. This is equivalent to sets defined by both a universal and existential formula in the language of second order arithmetic and to some models of <a href="Hypercomputation" title="Hypercomputation">Hypercomputation</a>. Even more general recursion theories have been studied, such as <b>E-recursion theory</b> in which any set can be used as an argument to an E-recursive function.

</p>

<div class="mw-heading mw-heading3"><h3 id="Hyper-computation">Hyper-computation</h3></div>

<p>Although the Church–Turing thesis states that the computable functions include all functions with algorithms, it is possible to consider broader classes of functions that relax the requirements that algorithms must possess. The field of <a href="Hypercomputation" title="Hypercomputation">Hypercomputation</a> studies models of computation that go beyond normal Turing computation.

</p>

<ul><li><a href="Computable_number" title="Computable number">Computable number</a></li>

<li><a href="Effective_method" title="Effective method">Effective method</a></li>

<li><a href="Theory_of_computation" title="Theory of computation">Theory of computation</a></li>

<li><a href="Recursion_theory" class="mw-redirect" title="Recursion theory">Recursion theory</a></li>

<li><a href="Turing_degree" title="Turing degree">Turing degree</a></li>

<li><a href="Arithmetical_hierarchy" title="Arithmetical hierarchy">Arithmetical hierarchy</a></li>

<li><a href="Hypercomputation" title="Hypercomputation">Hypercomputation</a></li>

<li><a href="Super-recursive_algorithm" title="Super-recursive algorithm">Super-recursive algorithm</a></li>

<li><a href="Semicomputable_function" title="Semicomputable function">Semicomputable function</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFEnderton2002" class="citation book cs1">Enderton, Herbert (2002). <i>A Mathematical Introduction to Logic</i> (Second ed.). USA: Elsevier. p. 209. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-12-238452-0</bdi>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFEnderton2002" class="citation book cs1">Enderton, Herbert (2002). <i>A Mathematical Introduction to Logic</i> (Second ed.). USA: Elsevier. p. 208,262. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-12-238452-0</bdi>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">C. J. Ash, J. Knight, <i>Computable Structures and the Hyperarithmetical Hierarchy</i> (Studies in Logic and the Foundation of Mathematics, 2000), p. 4</span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text">R. Soare, <a rel="nofollow" class="external text" href="http://www.people.cs.uchicago.edu/~soare/History/compute.pdf">Computability and Recursion</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20220331221004/http://www.people.cs.uchicago.edu/~soare/History/compute.pdf">Archived</a> 2022-03-31 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a> (1995). Accessed 9 November 2022.</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFPéter1935" class="citation journal cs1"><a href="R%C3%B3zsa_P%C3%A9ter" title="Rózsa Péter">Péter, Rózsa</a> (1935). "Konstruktion nichtrekursiver Funktionen". <i><a href="Mathematische_Annalen" title="Mathematische Annalen">Mathematische Annalen</a></i>. <b>111</b>: <span class="nowrap">42–</span>60. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2FBF01472200">10.1007/BF01472200</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:121107217">121107217</a>.</cite></span>

</li>

</ol></div></div>

<ul><li>Cutland, Nigel. <i>Computability</i>. Cambridge University Press, 1980.</li>

<li><a href="Herbert_Enderton" title="Herbert Enderton">Enderton, H.B.</a> Elements of recursion theory. <i>Handbook of Mathematical Logic</i> (North-Holland 1977) pp. 527–566.</li>

<li>Rogers, H. <i>Theory of recursive functions and effective computation</i> (McGraw–Hill 1967).</li>

<li><a href="A._Turing" class="mw-redirect" title="A. Turing">Turing, A.</a> (1937), <a rel="nofollow" class="external text" href="https://academic.oup.com/plms/issue/s2-42/1">On Computable Numbers, With an Application to the Entscheidungsproblem</a>. <i>Proceedings of the London Mathematical Society</i>, Series 2, Volume 42 (1937), p.230–265. Reprinted in M. Davis (ed.), <i>The Undecidable</i>, Raven Press, Hewlett, NY, 1965.</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Complexity_classes148" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Complexity_classes148" style="font-size:114%;margin:0 4em"><a href="Complexity_class" title="Complexity class">Complexity classes</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Considered feasible</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="DLOGTIME" title="DLOGTIME">DLOGTIME</a></li>

<ul><li><a href="NL-complete" title="NL-complete">NL-complete</a></li></ul></li>

<ul><li><a href="P-complete" title="P-complete">P-complete</a></li></ul></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Suspected infeasible</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="NP-completeness" title="NP-completeness">NP-complete</a></li>

<li><a href="Co-NP-complete" title="Co-NP-complete">co-NP-complete</a></li></ul></li>

<ul><li><a href="%E2%99%AFP-complete" title="♯P-complete">#P-complete</a></li></ul></li>

<li><a href="PSPACE" title="PSPACE">PSPACE</a>

<ul><li><a href="PSPACE-complete" title="PSPACE-complete">PSPACE-complete</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Considered infeasible</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="EXPTIME" title="EXPTIME">EXPTIME</a></li>

<li><a href="NEXPTIME" title="NEXPTIME">NEXPTIME</a></li>

<li><a href="EXPSPACE" title="EXPSPACE">EXPSPACE</a></li>

<li><a href="2-EXPTIME" title="2-EXPTIME">2-EXPTIME</a></li>

<li><a href="ELEMENTARY" title="ELEMENTARY">ELEMENTARY</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Class hierarchies</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Polynomial_hierarchy" title="Polynomial hierarchy">Polynomial hierarchy</a></li>

<li><a href="Exponential_hierarchy" title="Exponential hierarchy">Exponential hierarchy</a></li>

<li><a href="Grzegorczyk_hierarchy" title="Grzegorczyk hierarchy">Grzegorczyk hierarchy</a></li>

<li><a href="Arithmetical_hierarchy" title="Arithmetical hierarchy">Arithmetical hierarchy</a></li>

<li><a href="Boolean_hierarchy" title="Boolean hierarchy">Boolean hierarchy</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Families of classes</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="DTIME" title="DTIME">DTIME</a></li>

<li><a href="NTIME" title="NTIME">NTIME</a></li>

<li><a href="DSPACE" title="DSPACE">DSPACE</a></li>

<li><a href="NSPACE" title="NSPACE">NSPACE</a></li>

<li><a href="Probabilistically_checkable_proof" title="Probabilistically checkable proof">Probabilistically checkable proof</a></li>

<li><a href="Interactive_proof_system" title="Interactive proof system">Interactive proof system</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><a href="List_of_complexity_classes" title="List of complexity classes">List of complexity classes</a></div></td></tr></tbody></table></div>

<div class="navbox-styles"></div><div role="navigation" class="navbox" aria-labelledby="Mathematical_logic344" style="padding:3px"><table class="nowraplinks mw-collapsible mw-collapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><div id="Mathematical_logic344" style="font-size:114%;margin:0 4em"><a href="Mathematical_logic" title="Mathematical logic">Mathematical logic</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Axiom" title="Axiom">Axiom</a>

<li><a href="Cardinality" title="Cardinality">Cardinality</a></li>

<li><a href="First-order_logic" title="First-order logic">First-order logic</a></li>

<li><a href="Formal_proof" title="Formal proof">Formal proof</a></li>

<li><a href="Formal_semantics_(logic)" class="mw-redirect" title="Formal semantics (logic)">Formal semantics</a></li>

<li><a href="Foundations_of_mathematics" title="Foundations of mathematics">Foundations of mathematics</a></li>

<li><a href="Information_theory" title="Information theory">Information theory</a></li>

<li><a href="Lemma_(mathematics)" title="Lemma (mathematics)">Lemma</a></li>

<li><a href="Logical_consequence" title="Logical consequence">Logical consequence</a></li>

<li><a href="Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a></li>

<li><a href="Theorem" title="Theorem">Theorem</a></li>

<li><a href="Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a></li>

<li><a href="Type_theory" title="Type theory">Type theory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theorems (list)<br> and <a href="Paradoxes_of_set_theory" title="Paradoxes of set theory">paradoxes</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="G%C3%B6del's_completeness_theorem" title="Gödel's completeness theorem">Gödel's completeness</a> and <a href="G%C3%B6del's_incompleteness_theorems" title="Gödel's incompleteness theorems">incompleteness theorems</a></li>

<li><a href="Tarski's_undefinability_theorem" title="Tarski's undefinability theorem">Tarski's undefinability</a></li>

<li><a href="Banach%E2%80%93Tarski_paradox" title="Banach–Tarski paradox">Banach–Tarski paradox</a></li>

<li>Cantor's <a href="Cantor's_theorem" title="Cantor's theorem">theorem,</a> <a href="Cantor's_paradox" title="Cantor's paradox">paradox</a> and <a href="Cantor's_diagonal_argument" title="Cantor's diagonal argument">diagonal argument</a></li>

<li><a href="Compactness_theorem" title="Compactness theorem">Compactness</a></li>

<li><a href="Halting_problem" title="Halting problem">Halting problem</a></li>

<li><a href="Lindstr%C3%B6m's_theorem" title="Lindström's theorem">Lindström's</a></li>

<li><a href="L%C3%B6wenheim%E2%80%93Skolem_theorem" title="Löwenheim–Skolem theorem">Löwenheim–Skolem</a></li>

<li><a href="Russell's_paradox" title="Russell's paradox">Russell's paradox</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Logic" title="Logic">Logics</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><th id="Traditional95" scope="row" class="navbox-group" style="width:1%"><a href="Term_logic" title="Term logic">Traditional</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Classical_logic" title="Classical logic">Classical logic</a></li>

<li><a href="Logical_truth" title="Logical truth">Logical truth</a></li>

<li><a href="Tautology_(logic)" title="Tautology (logic)">Tautology</a></li>

<li><a href="Proposition" title="Proposition">Proposition</a></li>

<li><a href="Inference" title="Inference">Inference</a></li>

<li><a href="Logical_equivalence" title="Logical equivalence">Logical equivalence</a></li>

<li><a href="Consistency" title="Consistency">Consistency</a>

<ul><li><a href="Equiconsistency" title="Equiconsistency">Equiconsistency</a></li></ul></li>

<li><a href="Argument" title="Argument">Argument</a></li>

<li><a href="Soundness" title="Soundness">Soundness</a></li>

<li><a href="Validity_(logic)" title="Validity (logic)">Validity</a></li>

<li><a href="Syllogism" title="Syllogism">Syllogism</a></li>

<li><a href="Square_of_opposition" title="Square of opposition">Square of opposition</a></li>

<li><a href="Venn_diagram" title="Venn diagram">Venn diagram</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Boolean_algebra" title="Boolean algebra">Boolean algebra</a></li>

<li><a href="Boolean_function" title="Boolean function">Boolean functions</a></li>

<li><a href="Logical_connective" title="Logical connective">Logical connectives</a></li>

<li><a href="Propositional_calculus" class="mw-redirect" title="Propositional calculus">Propositional calculus</a></li>

<li><a href="Propositional_formula" title="Propositional formula">Propositional formula</a></li>

<li><a href="Truth_table" title="Truth table">Truth tables</a></li>

<li><a href="Many-valued_logic" title="Many-valued logic">Many-valued logic</a>

<li><a href="Finite-valued_logic" title="Finite-valued logic">finite</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Predicate_logic" class="mw-redirect" title="Predicate logic">Predicate</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="First-order_logic" title="First-order logic">First-order</a>

<li><a href="Second-order_logic" title="Second-order logic">Second-order</a>

<ul><li><a href="Monadic_second-order_logic" title="Monadic second-order logic">Monadic</a></li></ul></li>

<li><a href="Higher-order_logic" title="Higher-order logic">Higher-order</a></li>

<li><a href="Fixed-point_logic" title="Fixed-point logic">Fixed-point</a></li>

<li><a href="Quantifier_(logic)" title="Quantifier (logic)">Quantifiers</a></li>

<li><a href="Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a></li>

<li><a href="Monadic_predicate_calculus" title="Monadic predicate calculus">Monadic predicate calculus</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Set_theory" title="Set theory">Set theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Hereditary_set" title="Hereditary set">hereditary</a></li></ul></li>

<li><a href="Class_(set_theory)" title="Class (set theory)">Class</a></li>

<li>(<a href="Urelement" title="Urelement">Ur-</a>)<a href="Element_(mathematics)" title="Element (mathematics)">Element</a></li>

<li><a href="Ordinal_number" title="Ordinal number">Ordinal number</a></li>

<li><a href="Extensionality" title="Extensionality">Extensionality</a></li>

<li><a href="Forcing_(mathematics)" title="Forcing (mathematics)">Forcing</a></li>

<li><a href="Relation_(mathematics)" title="Relation (mathematics)">Relation</a>

<ul><li><a href="Equivalence_relation" title="Equivalence relation">equivalence</a></li>

<li><a href="Partition_of_a_set" title="Partition of a set">partition</a></li></ul></li>

<li>Set operations:

<ul><li><a href="Intersection_(set_theory)" title="Intersection (set theory)">intersection</a></li>

<li><a href="Union_(set_theory)" title="Union (set theory)">union</a></li>

<li><a href="Complement_(set_theory)" title="Complement (set theory)">complement</a></li>

<li><a href="Cartesian_product" title="Cartesian product">Cartesian product</a></li>

<li><a href="Power_set" title="Power set">power set</a></li>

<li><a href="List_of_set_identities_and_relations" title="List of set identities and relations">identities</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types of <a href="Set_(mathematics)" title="Set (mathematics)">sets</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Countable_set" title="Countable set">Countable</a></li>

<li><a href="Uncountable_set" title="Uncountable set">Uncountable</a></li>

<li><a href="Empty_set" title="Empty set">Empty</a></li>

<li><a href="Inhabited_set" title="Inhabited set">Inhabited</a></li>

<li><a href="Singleton_(mathematics)" title="Singleton (mathematics)">Singleton</a></li>

<li><a href="Finite_set" title="Finite set">Finite</a></li>

<li><a href="Infinite_set" title="Infinite set">Infinite</a></li>

<li><a href="Transitive_set" title="Transitive set">Transitive</a></li>

<li><a href="Ultrafilter_(set_theory)" class="mw-redirect" title="Ultrafilter (set theory)">Ultrafilter</a></li>

<li><a href="Recursive_set" class="mw-redirect" title="Recursive set">Recursive</a></li>

<li><a href="Fuzzy_set" title="Fuzzy set">Fuzzy</a></li>

<li><a href="Universal_set" title="Universal set">Universal</a></li>

<li><a href="Universe_(mathematics)" title="Universe (mathematics)">Universe</a>

<ul><li><a href="Constructible_universe" title="Constructible universe">constructible</a></li>

<li><a href="Grothendieck_universe" title="Grothendieck universe">Grothendieck</a></li>

<li><a href="Von_Neumann_universe" title="Von Neumann universe">Von Neumann</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Map_(mathematics)" title="Map (mathematics)">Maps</a> and <a href="Cardinality" title="Cardinality">cardinality</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Function_(mathematics)" title="Function (mathematics)">Function</a>/<a href="Map_(mathematics)" title="Map (mathematics)">Map</a>

<ul><li><a href="Domain_of_a_function" title="Domain of a function">domain</a></li>

<li><a href="Codomain" title="Codomain">codomain</a></li>

<li><a href="Image_(mathematics)" title="Image (mathematics)">image</a></li></ul></li>

<li><a href="Injective_function" title="Injective function">In</a>/<a href="Surjective_function" title="Surjective function">Sur</a>/<a href="Bijection" title="Bijection">Bi</a>-jection</li>

<li><a href="Schr%C3%B6der%E2%80%93Bernstein_theorem" title="Schröder–Bernstein theorem">Schröder–Bernstein theorem</a></li>

<li><a href="Isomorphism" title="Isomorphism">Isomorphism</a></li>

<li><a href="G%C3%B6del_numbering" title="Gödel numbering">Gödel numbering</a></li>

<li><a href="Enumeration" title="Enumeration">Enumeration</a></li>

<li><a href="Large_cardinal" title="Large cardinal">Large cardinal</a>

<ul><li><a href="Inaccessible_cardinal" title="Inaccessible cardinal">inaccessible</a></li></ul></li>

<li><a href="Aleph_number" title="Aleph number">Aleph number</a></li>

<li><a href="Operation_(mathematics)" title="Operation (mathematics)">Operation</a>

<ul><li><a href="Binary_operation" title="Binary operation">binary</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Set theories</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Zermelo%E2%80%93Fraenkel_set_theory" title="Zermelo–Fraenkel set theory">Zermelo–Fraenkel</a>

<ul><li><a href="Axiom_of_choice" title="Axiom of choice">axiom of choice</a></li>

<li><a href="Continuum_hypothesis" title="Continuum hypothesis">continuum hypothesis</a></li></ul></li>

<li><a href="General_set_theory" title="General set theory">General</a></li>

<li><a href="Kripke%E2%80%93Platek_set_theory" title="Kripke–Platek set theory">Kripke–Platek</a></li>

<li><a href="Morse%E2%80%93Kelley_set_theory" title="Morse–Kelley set theory">Morse–Kelley</a></li>

<li><a href="Naive_set_theory" title="Naive set theory">Naive</a></li>

<li><a href="New_Foundations" title="New Foundations">New Foundations</a></li>

<li><a href="Tarski%E2%80%93Grothendieck_set_theory" title="Tarski–Grothendieck set theory">Tarski–Grothendieck</a></li>

<li><a href="Von_Neumann%E2%80%93Bernays%E2%80%93G%C3%B6del_set_theory" title="Von Neumann–Bernays–Gödel set theory">Von Neumann–Bernays–Gödel</a></li>

<li><a href="Ackermann_set_theory" title="Ackermann set theory">Ackermann</a></li>

<li><a href="Constructive_set_theory" title="Constructive set theory">Constructive</a></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Formal_system" title="Formal system">Formal systems</a> (<a href="List_of_formal_systems" title="List of formal systems"><span style="font-size: 85%;">list</span></a>),<br><a href="Formal_language" title="Formal language">language</a> and <a href="Syntax_(logic)" title="Syntax (logic)">syntax</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em"></div><table class="nowraplinks navbox-subgroup" style="border-spacing:0"><tbody><tr><td colspan="2" class="navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Alphabet_(formal_languages)" title="Alphabet (formal languages)">Alphabet</a></li>

<li><a href="Arity" title="Arity">Arity</a></li>

<li><a href="Automata_theory" title="Automata theory">Automata</a></li>

<li><a href="Axiom_schema" title="Axiom schema">Axiom schema</a></li>

<li><a href="Expression_(mathematics)" title="Expression (mathematics)">Expression</a>

<ul><li><a href="Ground_expression" title="Ground expression">ground</a></li></ul></li>

<li><a href="Extension_by_new_constant_and_function_names" title="Extension by new constant and function names">Extension</a>

<ul><li><a href="Extension_by_definitions" class="mw-redirect" title="Extension by definitions">by definition</a></li>

<li><a href="Conservative_extension" title="Conservative extension">conservative</a></li></ul></li>

<li><a href="Finitary_relation" title="Finitary relation">Relation</a></li>

<li><a href="Formation_rule" title="Formation rule">Formation rule</a></li>

<li><a href="Formal_grammar" title="Formal grammar">Grammar</a></li>

<li><a href="Well-formed_formula" title="Well-formed formula">Formula</a>

<ul><li><a href="Atomic_formula" title="Atomic formula">atomic</a></li>

<li><a href="Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">closed</a></li>

<li><a href="Ground_formula" class="mw-redirect" title="Ground formula">ground</a></li>

<li><a href="Free_variables_and_bound_variables" title="Free variables and bound variables">Free/bound variable</a></li>

<li><a href="Formal_language" title="Formal language">Language</a></li>

<li><a href="Metalanguage" title="Metalanguage">Metalanguage</a></li>

<li><a href="Logical_connective" title="Logical connective">Logical connective</a>

<li><a href="Predicate_(mathematical_logic)" class="mw-redirect" title="Predicate (mathematical logic)">Predicate</a>

<ul><li><a href="Functional_predicate" title="Functional predicate">functional</a></li>

<li><a href="Predicate_variable" title="Predicate variable">variable</a></li>

<li><a href="Propositional_variable" title="Propositional variable">propositional variable</a></li></ul></li>

<li><a href="Formal_proof" title="Formal proof">Proof</a></li>

<li><a href="Quantifier_(logic)" title="Quantifier (logic)">Quantifier</a>

<li><a href="Sentence_(mathematical_logic)" title="Sentence (mathematical logic)">Sentence</a>

<ul><li><a href="Atomic_sentence" title="Atomic sentence">atomic</a></li>

<li><a href="Spectrum_of_a_sentence" title="Spectrum of a sentence">spectrum</a></li></ul></li>

<li><a href="Signature_(logic)" title="Signature (logic)">Signature</a></li>

<li><a href="String_(formal_languages)" class="mw-redirect" title="String (formal languages)">String</a></li>

<li><a href="Substitution_(logic)" title="Substitution (logic)">Substitution</a></li>

<li><a href="Symbol_(formal)" title="Symbol (formal)">Symbol</a>

<ul><li><a href="Uninterpreted_function" title="Uninterpreted function">function</a></li>

<li><a href="Logical_constant" title="Logical constant">logical/constant</a></li>

<li><a href="Non-logical_symbol" title="Non-logical symbol">non-logical</a></li>

<li><a href="Variable_(mathematics)" title="Variable (mathematics)">variable</a></li></ul></li>

<li><a href="Theory_(mathematical_logic)" title="Theory (mathematical logic)">Theory</a>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><span class="nowrap">Example <a href="Axiomatic_system" title="Axiomatic system">axiomatic<br>systems</a> <span style="font-size: 85%;">(<a href="List_of_first-order_theories" title="List of first-order theories">list</a>)</span></span></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>of <a href="True_arithmetic" title="True arithmetic">arithmetic</a>:

<ul><li><a href="Peano_axioms" title="Peano axioms">Peano</a></li>

<li><a href="Second-order_arithmetic" title="Second-order arithmetic">second-order</a></li>

<li><a href="Elementary_function_arithmetic" title="Elementary function arithmetic">elementary function</a></li>

<li><a href="Primitive_recursive_arithmetic" title="Primitive recursive arithmetic">primitive recursive</a></li>

<li><a href="Robinson_arithmetic" title="Robinson arithmetic">Robinson</a></li>

<li><a href="Skolem_arithmetic" title="Skolem arithmetic">Skolem</a></li></ul></li>

<li>of the <a href="Construction_of_the_real_numbers" title="Construction of the real numbers">real numbers</a>

<ul><li><a href="Tarski's_axiomatization_of_the_reals" title="Tarski's axiomatization of the reals">Tarski's axiomatization</a></li></ul></li>

<li>of <a href="Axiomatization_of_Boolean_algebras" class="mw-redirect" title="Axiomatization of Boolean algebras">Boolean algebras</a>

<ul><li><a href="Boolean_algebras_canonically_defined" title="Boolean algebras canonically defined">canonical</a></li>

<li><a href="Minimal_axioms_for_Boolean_algebra" title="Minimal axioms for Boolean algebra">minimal axioms</a></li></ul></li>

<li>of <a href="Foundations_of_geometry" title="Foundations of geometry">geometry</a>:

<ul><li><a href="Euclidean_geometry" title="Euclidean geometry">Euclidean</a>:

<ul><li><a href="Euclid's_Elements" title="Euclid's Elements"><i>Elements</i></a></li>

<li><a href="Hilbert's_axioms" title="Hilbert's axioms">Hilbert's</a></li>

<li><a href="Tarski's_axioms" title="Tarski's axioms">Tarski's</a></li></ul></li>

<li><a href="Non-Euclidean_geometry" title="Non-Euclidean geometry">non-Euclidean</a></li></ul></li></ul>

<ul><li><i><a href="Principia_Mathematica" title="Principia Mathematica">Principia Mathematica</a></i></li></ul>

</div></td></tr></tbody></table><div></div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Proof_theory" title="Proof theory">Proof theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Formal_proof" title="Formal proof">Formal proof</a></li>

<li><a href="Natural_deduction" title="Natural deduction">Natural deduction</a></li>

<li><a href="Logical_consequence" title="Logical consequence">Logical consequence</a></li>

<li><a href="Rule_of_inference" title="Rule of inference">Rule of inference</a></li>

<li><a href="Sequent_calculus" title="Sequent calculus">Sequent calculus</a></li>

<li><a href="Theorem" title="Theorem">Theorem</a></li>

<li><a href="Formal_system" title="Formal system">Systems</a>

<ul><li><a href="Axiomatic_system" title="Axiomatic system">axiomatic</a></li>

<li><a href="Deductive_system" class="mw-redirect" title="Deductive system">deductive</a></li>

<li><a href="Hilbert_system" title="Hilbert system">Hilbert</a>

<li><a href="Complete_theory" title="Complete theory">Complete theory</a></li>

<li><a href="Independence_(mathematical_logic)" title="Independence (mathematical logic)">Independence</a> (<a href="List_of_statements_independent_of_ZFC" title="List of statements independent of ZFC">from ZFC</a>)</li>

<li><a href="Proof_of_impossibility" title="Proof of impossibility">Proof of impossibility</a></li>

<li><a href="Ordinal_analysis" title="Ordinal analysis">Ordinal analysis</a></li>

<li><a href="Reverse_mathematics" title="Reverse mathematics">Reverse mathematics</a></li>

<li><a href="Self-verifying_theories" title="Self-verifying theories">Self-verifying theories</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Model_theory" title="Model theory">Model theory</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Interpretation_(logic)" title="Interpretation (logic)">Interpretation</a>

<ul><li><a href="Interpretation_function" class="mw-redirect" title="Interpretation function">function</a></li>

<li><a href="Interpretation_(model_theory)" title="Interpretation (model theory)">of models</a></li></ul></li>

<li><a href="Structure_(mathematical_logic)" title="Structure (mathematical logic)">Model</a>

<ul><li><a href="Elementary_equivalence" title="Elementary equivalence">equivalence</a></li>

<li><a href="Finite_model_theory" title="Finite model theory">finite</a></li>

<li><a href="Saturated_model" title="Saturated model">saturated</a></li>

<li><a href="Spectrum_of_a_theory" title="Spectrum of a theory">spectrum</a></li>

<li><a href="Substructure_(mathematics)" title="Substructure (mathematics)">submodel</a></li></ul></li>

<li><a href="Non-standard_model" title="Non-standard model">Non-standard model</a>

<ul><li><a href="Non-standard_model_of_arithmetic" title="Non-standard model of arithmetic">of arithmetic</a></li></ul></li>

<li><a href="Diagram_(mathematical_logic)" title="Diagram (mathematical logic)">Diagram</a>

<ul><li><a href="Elementary_diagram" title="Elementary diagram">elementary</a></li></ul></li>

<li><a href="Categorical_theory" title="Categorical theory">Categorical theory</a></li>

<li><a href="Model_complete_theory" title="Model complete theory">Model complete theory</a></li>

<li><a href="Satisfiability" title="Satisfiability">Satisfiability</a></li>

<li><a href="Semantics_of_logic" title="Semantics of logic">Semantics of logic</a></li>

<li><a href="Strength_(mathematical_logic)" title="Strength (mathematical logic)">Strength</a></li>

<li><a href="Theories_of_truth" class="mw-redirect" title="Theories of truth">Theories of truth</a>

<ul><li><a href="Semantic_theory_of_truth" title="Semantic theory of truth">semantic</a></li>

<li><a href="Tarski's_theory_of_truth" class="mw-redirect" title="Tarski's theory of truth">Tarski's</a></li>

<li><a href="Kripke's_theory_of_truth" class="mw-redirect" title="Kripke's theory of truth">Kripke's</a></li></ul></li>

<li><a href="T-schema" title="T-schema">T-schema</a></li>

<li><a href="Transfer_principle" title="Transfer principle">Transfer principle</a></li>

<li><a href="Truth_predicate" title="Truth predicate">Truth predicate</a></li>

<li><a href="Truth_value" title="Truth value">Truth value</a></li>

<li><a href="Ultraproduct" title="Ultraproduct">Ultraproduct</a></li>

<li><a href="Validity_(logic)" title="Validity (logic)">Validity</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computability_theory" title="Computability theory">Computability theory</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Church_encoding" title="Church encoding">Church encoding</a></li>

<li><a href="Church%E2%80%93Turing_thesis" title="Church–Turing thesis">Church–Turing thesis</a></li>

<li><a href="Computably_enumerable_set" title="Computably enumerable set">Computably enumerable</a></li>

<li><a href="Computable_set" title="Computable set">Computable set</a></li>

<li><a href="Decision_problem" title="Decision problem">Decision problem</a>

<ul><li><a href="Decidability_(logic)" title="Decidability (logic)">decidable</a></li>

<li><a href="Undecidable_problem" title="Undecidable problem">undecidable</a></li>

<li><a href="P_versus_NP_problem" title="P versus NP problem">P versus NP problem</a></li></ul></li>

<li><a href="Kolmogorov_complexity" title="Kolmogorov complexity">Kolmogorov complexity</a></li>

<li><a href="Lambda_calculus" title="Lambda calculus">Lambda calculus</a></li>

<li><a href="Primitive_recursive_function" title="Primitive recursive function">Primitive recursive function</a></li>

<li><a href="Recursion" title="Recursion">Recursion</a></li>

<li><a href="Recursive_set" class="mw-redirect" title="Recursive set">Recursive set</a></li>

<li><a href="Turing_machine" title="Turing machine">Turing machine</a></li>

<li><a href="Type_theory" title="Type theory">Type theory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Abstract_logic" title="Abstract logic">Abstract logic</a></li>

<li><a href="Algebraic_logic" title="Algebraic logic">Algebraic logic</a></li>

<li><a href="Automated_theorem_proving" title="Automated theorem proving">Automated theorem proving</a></li>

<li><a href="Category_theory" title="Category theory">Category theory</a></li>

<li><a href="Concrete_category" title="Concrete category">Concrete</a>/<a href="Category_(mathematics)" title="Category (mathematics)">Abstract category</a></li>

<li><a href="Category_of_sets" title="Category of sets">Category of sets</a></li>

<li><a href="History_of_logic" title="History of logic">History of logic</a></li>

<li><a href="History_of_mathematical_logic" class="mw-redirect" title="History of mathematical logic">History of mathematical logic</a>

<ul><li><a href="Timeline_of_mathematical_logic" title="Timeline of mathematical logic">timeline</a></li></ul></li>

<li><a href="Logicism" title="Logicism">Logicism</a></li>

<li><a href="Mathematical_object" title="Mathematical object">Mathematical object</a></li>

<li><a href="Philosophy_of_mathematics" title="Philosophy of mathematics">Philosophy of mathematics</a></li>

<li><a href="Supertask" title="Supertask">Supertask</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><b><span class="nowrap"><span class="skin-invert-image noviewer" typeof="mw:File"></span> </span><a href="Portal%3AMathematics" title="Portal:Mathematics">Mathematics portal</a></b></div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-05-22" href="https://en.wikipedia.org/wiki/?title=Computable_function&oldid=1291717451">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>